package q474_findMaxForm;

public class Solution {
    /**
     * 这道题还是很容易与背包问题产生联系的，但是需要考虑的是，背包问题只考虑了一个维度（物品的价值）
     * 而此题则需要考虑两个维度（1和0的数量）
     * 所以仍然要使用两个数组：
     * 我们把每一个字符串看成一个物品，它同时具有两个价值（1的价值和0的价值）
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String str : strs) {// 每一个字符串要看成一个物品
            // 计算每一个字符串中有多少个0和1
            int OneCount = 0, ZeroCount = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0'){
                    ZeroCount += 1;
                }else {
                    OneCount += 1;
                }
            }
            // 然后开始背包问题的循环
            // 由于我们的初始化是所有数组中的数都是0
            // 所以我们倒序遍历
            for (int i = m; i >= ZeroCount ; i--) {
                for (int j = n; j >= OneCount; j--) {
                    // 注意递推公式，这里需要考虑的是
                    // dp[i - ZeroCount][j - OneCount] + 1意味着
                    // dp[i - ZeroCount][j - OneCount]（包含i - ZeroCount 个 0 和 j - OneCount 个 1的最大字串长度）
                    // 所以我们如果要放当前这个字符串，那么就要付出当前字符串中0和1对应的容量 放了之后
                    // 意味着我们的字串相较于dp[i - ZeroCount][j - OneCount]多了 1 个
                    // 这个时候比较dp[i][j], dp[i - ZeroCount][j - OneCount] + 1来决定放还是不放
                    dp[i][j] = Math.max(dp[i][j], dp[i - ZeroCount][j - OneCount] + 1);
                }
            }
        }

        return dp[m][n];

    }
}
